package cn.edu.xjtu.data_structure.chapter01_linearlist.doublelinkedlist;

import cn.edu.xjtu.data_structure.chapter01_linearlist.ListADT;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/10 9:27
 */
public class DoubleLinkedList<E> implements ListADT<E> {
    //双链表的定义
    //带有表头结点header node
    private DLink<E> head;//头指针
    private DLink<E> tail;//尾指针
    protected DLink<E> curr;//指向当前元素前驱结点的指针

    //初始化与构造器
    private void setUp() {
        curr = head = tail = new DLink<E>(null, null);
    }

    public DoubleLinkedList() {
        setUp();
    }

    public DoubleLinkedList(int sz) {
        setUp();
    }

    @Override
    public void clear() {
        head.setNext(null);
        head.setPrev(null);
        curr = tail = head;
    }

    @Override
    public void insert(E it) {//插入元素
        if (curr == null) {
            System.out.println("no current element");
            return;
        }
        curr.setNext(new DLink(it, curr, curr.getNext()));
        //插完以后
        if (curr.getNext().getNext() != null) {
            curr.getNext().getNext().setPrev(curr.getNext());
        }
        if (tail == curr) {
            tail = tail.getNext();
        }//尾部插入

    }

    @Override
    public void append(E it) {//往尾部插入元素
        tail.setNext(new DLink(it, tail, null));
        tail = tail.getNext();
    }

    @Override
    public E remove() {//删除当前位置的元素
        if (!isInList()) {
            System.out.println("no current element");
            return null;
        }
        E it = (E) curr.getNext().getElement();
        if (curr.getNext().getNext() != null) {
            curr.getNext().getNext().setPrev(curr);
        } else {
            tail = curr;//删除最后一个元素，尾指针前移
        }
        curr.setNext(curr.getNext().getNext());
        return it;
    }

    @Override
    public void setFirst() {
        curr = head;
    }

    @Override
    public void prev() {
        if (curr != null) curr = curr.getPrev();//前移
    }

    @Override
    public void next() {
        if (curr != null) curr = curr.getNext();//后移
    }

    @Override
    public void setPosition(int position) {
        curr = head;
        for (int i = 0; (curr != null) && (i < position); i++) {
            curr = curr.getNext();//从头开始找
        }
    }

    @Override
    public void setValue(E it) {
        if (!isInList()) {
            System.out.println("no current element");
            return;
        }
        curr.getNext().setElement(it);
    }

    @Override
    public E currValue() {
        if (!isInList()) return null;
        return (E) curr.getNext().getElement();
    }

    @Override
    public int length() {
        int count = 0;
        for (DLink temp = head.getNext(); temp != null; temp = temp.getNext()) {
            count++;
        }
        return count;
    }

    @Override
    public boolean isInList() {
        return (curr != null) && (curr.getNext() != null);
    }

    @Override
    public boolean isFull() {
        return false;
    }

    @Override
    public boolean isEmpty() {
        return head.getNext() == null;
    }

    @Override
    public void print() {
        if (isEmpty()) {
            System.out.println("empty");
        } else {
            System.out.print("(");
            for (setFirst(); isInList(); next()) {
                System.out.print(currValue() + " ");
            }
            System.out.println(")");
        }
    }
}
